package com.yfbao.horizon.sudoku;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MixedSudoku {

    private static List<List<MatrixDto>> sourList = new ArrayList<>();
    private static final int sourMatrixOrder = 3;

    private static List<List<List<MatrixDto>>> optionalList = new ArrayList<>();

    public static void main(String[] args) {
        initData();
        printListMatrix(null);
        System.out.println("      \r\n");
        System.out.println("      \r\n");
//        testUUID();
        calcSudokuMatrix();
        finishCalc();
//        calc();
//        printListMatrix();

    }

    private static void finishCalc(){
        List<List<MatrixDto>> lists = copyMatrixList(sourList);
        List<List<List<MatrixDto>>> resList =new ArrayList<>();
        calcSudoku(sourList,lists,resList,0,0);

        int num=0;
        for (List<List<MatrixDto>> listList : resList) {
            num++;
            System.out.println("      \r\n");
            System.out.println(" -------"+num+"--------");
            System.out.println("      \r\n");
            printListMatrix(listList);
            System.out.println("      \r\n");

        }
    }

    private static void calcSudoku(List<List<MatrixDto>> list, List<List<MatrixDto>> targetList,List<List<List<MatrixDto>>> resList, int irow, int icolumn) {
        if (list == null) {
            list = sourList;
        }
        boolean isTop = true;
        for (int row = irow; row < list.size(); row++) {
            List<MatrixDto> matrixDtos = list.get(row);
            if (!isTop) {
                icolumn = 0;
            }
            for (int column = icolumn; column < matrixDtos.size(); column++) {
                MatrixDto matrixDto = matrixDtos.get(column);
                List<MatrixDto> sourMatrixList = matrixDto.getSourMatrixList();
                if (sourMatrixList == null) {
                    throw new RuntimeException("请先计算数据备选值");
                }
                boolean findValue=false;
                for (int i = 0; i < sourMatrixList.size(); i++) {
                    MatrixDto targerMatrix = sourMatrixList.get(i);
                    boolean useful = isUseful(targetList, targerMatrix);
                    if (!useful) {
                        continue;
                    }
                    List<MatrixDto> rowMatrix = targetList.get(row);
                    MatrixDto tgMatrix = copyMatrix(targerMatrix);
                    rowMatrix.set(column, tgMatrix);
                    Integer order = targerMatrix.getOrder();
                    findValue =true;
                    if (row == (order - 1) && column == (order - 1)) {
                        //todo:满足条件的targetList
                        resList.add(targetList);
                        continue;
                    }else{
                        //拷贝新的list ,然后继续计算
                        List<List<MatrixDto>> newTarList = copyMatrixList(targetList);
                        calcSudoku(list, newTarList,resList, row, column+1);
                    }
                }
                if(!findValue){
                    return;
                }
            }
            isTop = false;
        }

    }

    private static List<List<MatrixDto>> copyMatrixList(List<List<MatrixDto>> srcList){
        List<List<MatrixDto>> tarList = new ArrayList<>();
        for(int row=0;row<sourMatrixOrder;row++){
            List<MatrixDto> list =  new ArrayList<>();
            for(int column=0;column<sourMatrixOrder;column++){
                list.add(null);
            }
            tarList.add(list);
        }
        for (int i = 0; i < srcList.size(); i++) {
            List<MatrixDto> matrixDtos = srcList.get(i);

            List<MatrixDto> tarMatrixDtos = tarList.get(i);
            if(tarMatrixDtos ==null){
                tarMatrixDtos =new ArrayList<>();
                tarList.set(i,tarMatrixDtos);
            }

            for (int j = 0; j < matrixDtos.size(); j++) {
                MatrixDto matrixDto = matrixDtos.get(j);
                MatrixDto tarMatr = copyMatrix(matrixDto);
                tarMatrixDtos.set(j,tarMatr);
            }
        }
        return tarList;
    }


   private static boolean isUseful(List<List<MatrixDto>>  srcList,MatrixDto targetMatrix){
//        printListMatrix(srcList);
//       System.out.println("   \r\n");
//       printMatrixDto(targetMatrix);

       String key = targetMatrix.getKey();
       String[] split = key.split(",");
       Integer order = targetMatrix.getOrder();
       Integer rowNum = Integer.valueOf(split[0]);
       Integer columnNum = Integer.valueOf(split[1]);
       List<MatrixDto> rowMatrixList =new ArrayList<>();
       List<MatrixDto> columnMatrixList =new ArrayList<>();
       for (int row = 0; row < order; row++) {

           MatrixDto matrixDto = srcList.get(row).get(columnNum);
           if(row==rowNum){
               matrixDto= targetMatrix;
           }
           if(matrixDto!=null){
               columnMatrixList.add(matrixDto);
           }
       }
       for (int column = 0; column < order; column++) {
           MatrixDto matrixDto = srcList.get(rowNum).get(column);
           if(column == columnNum){
               matrixDto =targetMatrix;
           }
           if(matrixDto!=null){
               rowMatrixList.add(matrixDto);
           }
       }
       Set<Integer> valueSet = new HashSet<>();
       for(int iRow=0;iRow<order;iRow++){
           for (MatrixDto matrixDto : rowMatrixList) {
               for(int iColumn=0;iColumn<order;iColumn++){
                   IndexValueDto value = matrixDto.getValue(iRow, iColumn);
                   if(value.getCurrentValue()!=0 && valueSet.contains(value.getCurrentValue())){
                       return false;
                   }
                   valueSet.add(value.getCurrentValue());
               }
           }
           valueSet.clear();
       }

       for(int iColumn=0;iColumn<order;iColumn++){
           for (MatrixDto matrixDto : columnMatrixList) {
               for(int iRow=0;iRow<order;iRow++){
                   IndexValueDto value = matrixDto.getValue(iRow, iColumn);
                   if(value.getCurrentValue()!=0 && valueSet.contains(value.getCurrentValue())){
                       return false;
                   }
                   valueSet.add(value.getCurrentValue());
               }
           }
           valueSet.clear();
       }
       return true;
   }



    private static void calcSudokuMatrix(){
        for(int row=0;row<sourMatrixOrder;row++){
            for(int column=0;column<sourMatrixOrder;column++){
                MatrixDto matrixDto = sourList.get(row).get(column);
                List<MatrixDto> matrixDtos = calcSudokuMatrix(matrixDto);
                System.out.println(String.format("matrix list size %d,%d: %s",row,column,matrixDtos.size()));
//                lists.add(column,matrixDtos);
                matrixDto.setSourMatrixList(matrixDtos);
//                for (MatrixDto dto : matrixDtos) {
//                    printMatrixDto(dto);
//                    System.out.println("--------------------------------");
//                }
            }
        }

//        MatrixDto matrixDto = sourList.get(0).get(0);
//        printMatrixDto(matrixDto);
//        List<MatrixDto> matrixDtos = calcSudokuMatrix(matrixDto);
//        System.out.println("matrix list size:"+matrixDtos.size());
//        for (MatrixDto dto : matrixDtos) {
//            printMatrixDto(dto);
//            System.out.println("--------------------------------");
//        }
    }

    /**
     * 初始化矩阵
     */
    public static void initData(){
        //初始化格式，  0,0;0,0,0
        List<String> initlist = new ArrayList<>();
//        initlist.add("0,0;0,1,2");
//        initlist.add("0,0;1,0,3");
//        initlist.add("0,1;1,1,2");
//        initlist.add("1,0;1,0,4");
//        initlist.add("1,1;0,0,4");
//        initlist.add("1,1;1,0,2");

        initlist.add("0,0;0,1,6");  initlist.add("0,0;1,0,3"); initlist.add("0,0;2,0,7");  initlist.add("0,0;2,2,1");
        initlist.add("0,1;0,0,3");  initlist.add("0,1;0,2,2"); initlist.add("0,1;2,0,5");
        initlist.add("0,2;0,2,1"); initlist.add("0,2;1,1,6");  initlist.add("0,2;1,2,8");  initlist.add("0,2;2,0,9");

        initlist.add("1,0;0,1,8"); initlist.add("1,0;1,0,9"); initlist.add("1,0;2,0,6"); initlist.add("1,0;2,2,7");
        initlist.add("1,1;0,0,9"); initlist.add("1,1;0,2,3"); initlist.add("1,1;1,1,2"); initlist.add("1,1;2,2,1");
        initlist.add("1,2;0,0,7"); initlist.add("1,2;2,0,2"); initlist.add("1,2;2,1,5");

        initlist.add("2,0;0,0,1"); initlist.add("2,0;0,2,9"); initlist.add("2,0;1,1,5"); initlist.add("2,0;2,1,2");
        initlist.add("2,1;0,2,6"); initlist.add("2,1;1,0,7"); initlist.add("2,1;1,1,4"); initlist.add("2,1;2,2,5");
        initlist.add("2,2;1,1,3");



        initMatrix(initlist);
    }

    private static void initMatrix(List<String> initlist){

        if(sourList.isEmpty()){

            for(int row=0;row<sourMatrixOrder;row++){
                List<MatrixDto> list =  new ArrayList<>();
                for(int column=0;column<sourMatrixOrder;column++){
                    list.add(null);
                }
                sourList.add(list);
            }


            for(int i = 0; i< sourMatrixOrder; i++){
                List<MatrixDto> matrixDtos = sourList.get(i);
                for(int j = 0; j< sourMatrixOrder; j++){
                    MatrixDto matrixDto = new MatrixDto(sourMatrixOrder,i+","+j);
                    matrixDtos.set(j,matrixDto);
                }
            }
        }
        for (String s : initlist) {
            String[] split = s.split(";");
            String[] matrixIndex = split[0].split(",");
            MatrixDto matrixDto = sourList.get(Integer.valueOf(matrixIndex[0])).get(Integer.valueOf(matrixIndex[1]));
            String[] split1 = split[1].split(",");
            matrixDto.initData(Integer.valueOf(split1[0]),Integer.valueOf(split1[1]),Integer.valueOf(split1[2]));
        }
    }

    private static void printListMatrix(List<List<MatrixDto>> lists) {
        if(lists ==null){
            lists=sourList;
        }
        for (int i = 0; i < sourMatrixOrder; i++) {
            for(int row = 0; row< sourMatrixOrder; row++) {
                for (int j = 0; j < sourMatrixOrder; j++) {
                    MatrixDto matrixDto = lists.get(i).get(j);
                    for (int column = 0; column < sourMatrixOrder; column++) {
                        if(matrixDto.getValue(row, column).getCurrentValue()==0){
                            System.out.print("-");
                        }else {
                            System.out.print(matrixDto.getValue(row, column).getCurrentValue());
                        }
                        System.out.print("   ");
                    }
                    if(j<(sourMatrixOrder -1)){
                        System.out.print("|  ");
                    }
                }
                System.out.println(" ");
            }
            if(i<(sourMatrixOrder -1)){
                System.out.println("--------------------------------------");
            }
        }
    }

    private static void printMatrixDto(MatrixDto matrixDto){
        Integer order = matrixDto.getOrder();
        for(int row=0;row<order;row++){
            for(int column=0;column<order;column++){
                Integer currentValue = matrixDto.getValue(row, column).getCurrentValue();
                System.out.print(matrixDto.getValue(row, column).getCurrentValue());
                System.out.print("   ");
            }
            System.out.println(" ");
        }
    }

    private static void calc(){
        for(int row = 0; row< sourMatrixOrder; row++){
            try {
                for(int column = 0; column< sourMatrixOrder; column++){
                    try {
                        calcValue(row,column);
                    }catch (RuntimeException e){
                        if(column>=0){
                            System.out.println("递归矩阵-列："+e.getMessage());
                            column=column-1;
                        }else {
                            sourList.get(row).get(column).clear();
                            throw new RuntimeException("重新选矩阵-行");
                        }
                    }
                }
            }catch (RuntimeException ee){
                if(row>=0){
                    System.out.println("递归矩阵-行："+ee.getMessage());
                    row=row-1;
                }else {
                    throw new RuntimeException("计算失败");
                }
            }
        }
    }

    private static void calcValue(int row,int column) {
        MatrixDto juZhen = sourList.get(row).get(column);
        for (int i = 0; i < sourMatrixOrder; i++) {
            try {
                for (int j = 0; j < sourMatrixOrder; j++) {
                    IndexValueDto value = juZhen.getValue(i, j);
                    try {
                        if(value.getCurrentValue() ==0){
                            for(int num = 1; num<=(sourMatrixOrder * sourMatrixOrder); num++){
                                //判断自己是否可以设置此值
                                if(value.isInvalid(num)){
                                    continue;
                                }
                                //判断小矩阵内是否已经存在此值
                                if(juZhen.containValue(num)){
                                    continue;
                                }
                                //判断大矩阵行、列是否存在此值
                                if(listMartixContainValue(num,row,column,i,j)){
                                    continue;
                                }
                                juZhen.setValue(i,j,num);
                                break;
                            }
                        }
                        Integer currentValue = juZhen.getValue(i, j).getCurrentValue();
                        if(currentValue==0){
//                            juZhen.getValue(i, j).clear();
                            throw new RuntimeException("---");
                        }
                    }catch (RuntimeException e){
                        System.out.println("赋值异常"+e.getMessage());
                        if(j>=0){
                            juZhen.getValue(i, j).clear();
                            j=j-1;
                        }else {
                            throw new RuntimeException("");
                        }
                    }
                }
            }catch (RuntimeException ee){
                System.out.println("赋值异常A"+ee.getMessage());
                if(i>=0){
                    //还原所有行
                    i=i-1;
                }else {
                    juZhen.clear();
                    throw new RuntimeException("");
                }
            }

        }
    }

    private static boolean listMartixContainValue(int value, int row, int column, int i, int j){
        for(int iRow = 0; iRow< sourMatrixOrder; iRow++){
            MatrixDto juZhen = sourList.get(row).get(iRow);
            for(int jj = 0; jj< sourMatrixOrder; jj++){
                Integer value1 = juZhen.getValue(i, jj).getCurrentValue();
                if(value == value1){
                    return true;
                }
            }
        }

        for(int jColumn = 0; jColumn< sourMatrixOrder; jColumn++){
            MatrixDto juZhen = sourList.get(jColumn).get(column);
            for(int ii = 0; ii< sourMatrixOrder; ii++){
                Integer value1 = juZhen.getValue(ii, j).getCurrentValue();
                if(value == value1){
                    return true;
                }
            }
        }

        return false;
    }

    public static List<MatrixDto> calcSudokuMatrix(MatrixDto sourceMatrix){
        List<MatrixDto> list =new ArrayList<>();
        calcSudoku(list,sourceMatrix,0,0);
        return list;
    }

    private static void calcSudoku(List<MatrixDto> list, MatrixDto sourceMatrixDto, int row, int column){
        if(sourceMatrixDto.isFinished()){
            list.add(sourceMatrixDto);
            return;
        }
        Integer matrixOrder = sourceMatrixDto.getMatrixOrder();
        boolean isTop=true;
        for(int iRow=row;iRow<matrixOrder;iRow++){
            if(!isTop){
                column=0;
            }
            for(int iColumn=column;iColumn<matrixOrder;iColumn++){
                IndexValueDto value = sourceMatrixDto.getValue(iRow, iColumn);
                if(value.getCurrentValue()==0){
                    List<Integer> availableValue = sourceMatrixDto.getAvailableValue();
                    for (Integer availabVau : availableValue) {
                        MatrixDto matrixDto = copyMatrix(sourceMatrixDto);
                        String[] split = matrixDto.getKey().split(",");
                        Integer matrixRow =Integer.valueOf(split[0]);
                        Integer matrixColumn =Integer.valueOf(split[1]);
                        boolean b = listMartixContainValue(availabVau, matrixRow, matrixColumn, iRow, iColumn);
                        if(b){
                            continue;
                        }
                        matrixDto.setValue(iRow,iColumn,availabVau);
                        if(matrixDto.isFinished()){
                            list.add(matrixDto);
                        }else {
                            calcSudoku(list,matrixDto,iRow,iColumn);
                        }
                    }
                }
            }
            isTop=false;
        }
    }


    private static MatrixDto copyMatrix(MatrixDto matrixDto){
        Integer matrixOrder = matrixDto.getMatrixOrder();
        MatrixDto newMatrixDto = new MatrixDto(matrixOrder,matrixDto.getKey());
        for(int row=0;row<matrixOrder;row++){
            for(int column=0;column<matrixOrder;column++){
                IndexValueDto value = matrixDto.getValue(row, column);
                if(value.getCurrentValue() ==0){
                    continue;
                }
                newMatrixDto.setValue(row,column,value.getCurrentValue());
            }
        }
        return newMatrixDto;
    }

}
